// 滑动窗口最大值问题
// 给定一个数组nums和滑动窗口的大小k，请找出所有滑动窗口里的最大值
//输入：nums=[1,3,-1,-1,5,3,6,7] k = 3
//输出：[3,3,5,5,6,7]
//暴力求解
var nums=[1,3,-1,-1,5,3,6,7],k = 3;
var maxSlidingWindow  = function (nums,k) {
    if(k === 1) return nums;
    let result = [],arr = [];
    for(let i = 0;i < nums.length;i ++){
        arr.push(nums[i]);
        if(i >= k - 1){
            result.push(Math.max(...arr));
            arr.shift();
        }
    }
    return result;
};
//优化，双端队列
var maxSlidingWindow = function (nums,k) {
    const deque = [];
    const result = [];
    for(let i = 0;i < nums.length;i ++){
        if(i - deque[0] >= k){
            deque.shift();
        }
        while(nums[deque[deque.length-1]] < nums[i]) deque.pop();
        deque.push(i);
        if(i >= k -1)   result.push(nums[deque[0]])
    }
    return result;
};
console.log(maxSlidingWindow(nums,k));